//Given a characters array tasks, representing the tasks a CPU needs to do, 
//where each letter represents a different task. Tasks could be done in any order. 
//Each task is done in one unit of time. For each unit of time, the CPU could 
//complete either one task or just be idle. 
//
// However, there is a non-negative integer n that represents the cooldown 
//period between two same tasks (the same letter in the array), that is that there 
//must be at least n units of time between any two same tasks. 
//
// Return the least number of units of times that the CPU will take to finish 
//all the given tasks. 
//
// 
// Example 1: 
//
// 
//Input: tasks = ["A","A","A","B","B","B"], n = 2
//Output: 8
//Explanation: 
//A -> B -> idle -> A -> B -> idle -> A -> B
//There is at least 2 units of time between any two same tasks.
// 
//
// Example 2: 
//
// 
//Input: tasks = ["A","A","A","B","B","B"], n = 0
//Output: 6
//Explanation: On this case any permutation of size 6 would work since n = 0.
//["A","A","A","B","B","B"]
//["A","B","A","B","A","B"]
//["B","B","B","A","A","A"]
//...
//And so on.
// 
//
// Example 3: 
//
// 
//Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
//Output: 16
//Explanation: 
//One possible solution is
//A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle ->
// idle -> A
// 
//
// 
// Constraints: 
//
// 
// 1 <= task.length <= 10⁴ 
// tasks[i] is upper-case English letter. 
// The integer n is in the range [0, 100]. 
// 
// Related Topics Array Hash Table Greedy Sorting Heap (Priority Queue) 
//Counting 👍 5761 👎 1079


package leetcode.editor.en;

import java.util.Arrays;

public class _621_TaskScheduler {
    public static void main(String[] args) {
        Solution solution = new _621_TaskScheduler().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int leastInterval(char[] tasks, int n) {
            if (n == 0) {
                return tasks.length;
            }
            int[] bulket = new int[26];
            for (char task : tasks) {
                bulket[task-'A'] += 1;
            }
            Arrays.sort(bulket);
            int maxCount = bulket[25];
            int count = 1;
            for (int i = bulket.length-1; i >= 1; i--) {
                if (bulket[i] == bulket[i-1]){
                    count++;
                }else {
                    break;
                }
            }
            int res = (maxCount-1)*(n+1)+count;
            return Math.max(res, tasks.length);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}